package myself.a011HowAreYou;

import java.util.Arrays;
import java.util.TreeSet;

/**
 * @author 叶之越
 * Description 求字符串数组中组合拼接中的字典序最小的情况
 * Date 2021/1/30
 * Time 13:44
 * Mail 739153436@qq.com
 */
public class LowestLexicography {

    public static String lowestString1(String[] arr) {
        if (arr == null || arr.length == 0) {
            return "";
        }
        TreeSet<String> result = proccess(arr);
        return result.first();
    }

    public static TreeSet<String> proccess(String[] arr) {
        TreeSet<String> ans = new TreeSet<>();
        if (arr.length == 0) {
            ans.add("");
            return ans;
        }
        for (int i = 0; i < arr.length; i++) {
            String head = arr[i];
            String[] next = removeString(arr, i);
            TreeSet<String> permutations = proccess(next);
            for (String permutation : permutations) {
                ans.add(head + permutation);
            }
        }
        return ans;
    }

    // 暴力解决方案，直接罗列所有排列组合进行求解
/*    public static String lowestString1(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        TreeSet<String> result = process(strs);
        return result.pollFirst();
    }

    public static TreeSet<String> process(String[] strs) {
        TreeSet<String> ans = new TreeSet<>();
        if (strs.length == 0) {
            ans.add("");
            return ans;
        }
        for (int i = 0; i < strs.length; i++) {
            String cur = strs[i];
            String[] next = removeString(strs, i);
            TreeSet<String> now = process(next);
            for (String s : now) {
                ans.add(cur + s);
            }
        }
        return ans;
    }*/

    private static String[] removeString(String[] arr, int index) {
        String[] result = new String[arr.length - 1];
        int nowIndex = 0;
        for (int j = 0; j < arr.length; j++) {
            if (j == index) {
                continue;
            }
            result[nowIndex++] = arr[j];
        }
        return result;
    }


    // 贪心算法，根据想法进行试验
    public static String lowestString2(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        Arrays.sort(strs, (o1, o2) -> (o1 + o2).compareTo(o2 + o1));
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < strs.length; i++) {
            builder.append(strs[i]);
        }
        return builder.toString();
    }
}
